/*
 * JBeagle - a Java toolkit for genetic algorithms.
 * 
 * Copyright (c) 2010 Matthijs Snel
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package jbeagle.core.ops;

import java.util.Collections;

import jbeagle.core.Population;
import jbeagle.core.ListIndividual;


public class SimpleCrossover<I extends ListIndividual<G>, G> implements CrossoverOperator<I, G> {

	protected double rate;
	
	public SimpleCrossover() {
		rate = CrossoverOperator.DEFAULT_RATE;
	}
	
	/**
	 * @param rate The crossover rate.
	 */
	public SimpleCrossover( double rate ) {
		setRate( rate );
	}
	
	/**
	 * Applies crossover to an intermediate population. Loops through the population,
	 * selects two random parents and applies crossover with a probability equal to 
	 * the crossover rate. The children (either crossover products or
	 * exact copies of the parents) are placed into the next population.
	 * <p>
	 * If the population size is uneven, a direct copy of the best (elite) individual will
	 * be placed into the next population.
	 * <p>
	 * Bear in mind that if crossover is applied, the original parent objects are modified,
	 * i.e. no new objects are created for the children. This means that the original population
	 * passed in as argument to the function will change as well.
	 * 
	 * @param pop	The population on which to apply crossover
	 * @return		The new population after crossover
	 * @see jbeagle.core.ops.GeneticOperator#apply(jbeagle.core.Population)
	 */
	public Population<I, G> apply( Population<I, G> pop ) {
		Population<I, G> nextPop = new Population<I, G>( pop.size() );
		I ind1, ind2;
		int i;
		
		//If population size is uneven, place direct copy of best individual into next pop
		if ( pop.size() % 2 > 0 ) {
			i = pop.indexOf( pop.getFittest() );
			nextPop.add( pop.remove(i) );
		}
		
		//Randomise order of individuals
		Collections.shuffle(pop);
		
		i = 0;
		while (i < pop.size()) {
			ind1 = pop.get(i++);
			ind2 = pop.get(i++);
		
			if ( Math.random() < rate )
				apply( ind1, ind2 );
			
			nextPop.add(ind1);
			nextPop.add(ind2);
		}
		
		return nextPop;
	}
		
	/**
	 * Applies single-point crossover to two <code>Individuals</code>. The crossover point 
	 * is chosen based on the length of the first individual (based on the assumption that 
	 * the order in which Individuals will be passed into the function is always random); thus,
	 * if the first is longer than the second, and the crossover point lies beyond the
	 * length of the second individual, genetic information will removed from individual 1
	 * and added to individual 2. Individual 1 will receive no genetic information from
	 * individual 2 in this case.
	 * <p>
	 * If individual 1 is of the same length or shorter than individual 2, genetic information
	 * will always be exchanged between the two individuals. 
	 * 
	 * @param i1 First individual on which to apply crossover. Length of this individual will
	 * be used to determine the crossover point.
	 * @param i2 Second individual on which to apply crossover.
	 * @see jbeagle.core.ops.CrossoverOperator#apply(ga.Individual, ga.Individual)
	 */
	public void apply( I parent1, I parent2 ) {

		int i1len = parent1.size(),
			i2len = parent2.size(),
			cpoint = 1 + (int) Math.round(Math.random() * (i1len-2));

		parent2.addAll( parent1.subList(cpoint, i1len) );
		parent1.removeRange(cpoint, i1len);
		
		//check for individuals of different lengths
		if ( cpoint < i2len ) {
			parent1.addAll( parent2.subList(cpoint, i2len) );
			parent2.removeRange(cpoint, i2len);
		}
	}
	
	/**
	 * Returns the current crossover rate.
	 * 
	 * @return The crossover rate.
	 * @see jbeagle.core.ops.GeneticOperator#getRate()
	 */
	public double getRate() {
		return rate;
	}
	
	/**
	 * Sets the current crossover rate.
	 * 
	 * @param r The desired crossover rate.
	 * @see jbeagle.core.ops.GeneticOperator#setRate( double )
	 */
	public void setRate( double r ) {
		rate = r;
	}
}
